package 树.BST;

import java.util.ArrayList;
import java.util.List;

/*
解题思路：
   遍历二叉树，把它的所有节点加入到一个list中。再遍历整个list，把两两元素相加的和与k作比较。相等返回true，否则返回false;
*/
public class 两数之和IV输入BST_653 {

    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        findAllRoot(list, root);
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                int num = list.get(i) + list.get(j);
                if (num == k) {
                    return true;
                }
            }
        }

        return false;
    }

    public void findAllRoot(List<Integer> list, TreeNode root) {//找到所有节点的值，并加入到list中
        if (root == null) {
            return;
        }

        list.add(root.val);
        findAllRoot(list, root.left);
        findAllRoot(list, root.right);

    }
}
